Матч 305, Нечестный дележ (UnfairDivision)

Дивизион 1, Уровень 2; Дивизион 2, Уровень 1

Альберт и его две сестры Бетти и Карина делят имущество. Стоимости вещей, доставшихся в наследство, выписаны на куске бумаги и задаются массивом assets. Альберт берет ножницы и разрезает бумагу между некоторыми двумя числами. Потом Бетти таким же образом разрезает один из кусков. Далее Карина выбирает кусок с максимальной суммой. Из оставшихся двух кусков выбор делает Бетти. Последний кусок достается Альберту.

Каждый из участников при выборе старается получить максимальную сумму наследства. Сестры обижены на брата, и в своих выборах будут наказывать его, если только при этом не пострадает их прибыль. Например, если у одной из сестер есть два разные варианта получить одну и туже сумму имущества, то она выберет тот из вариантов, при котором ее сестра получит больше.

Найти максимальную сумму, которую может обеспечить Альберт своим первым разрезом.

Класс: UnfairDivision

Метод: int albertsShare(vector<int> assets)

Ограничения: assets содержит от 3 до 50 элементов, 1 £ assets[i] £ 1000.

Вход. Массив assets, содержащий стоимости элементов имущества.

Выход. Максимальная сумма, которую может обеспечить себе Альберт своим выбором.

Пример входа

assets

{50, 90, 10, 100}

{1, 1, 1, 1, 1, 1, 1, 1, 1}

{1, 2, 3, 4, 5, 6, 7, 8, 9}

{5, 5, 5}

Пример выхода

50

2

10

5

РЕШЕНИЕ

перебор

Рассматриваем все возможные варианты разреза куска бумаги Альбертом. Пусть он делает разрез после числа a. Далее перебираем все возможные разрезы Бетти. Пусть она делает разрез после числа b (b ¹ a). Ищем суммы чисел, записанных на трех кусках бумаги, сортируем их по возрастанию в массиве s. Карина получает максимальную сумму наследства, равную s[2]. Бетти берет кусок с суммой s[1], Альберту достается s[0]. Для заданного a, перебирая все возможные значения b, находим наилучший выбор Бетти. При этом если текущий выбор Бетти s[1] равен ее наилучшему bestBetty, то выбираем тот, при котором Альберту достанется меньше. Среди всех разрезов Альберта выбираем тот, при котором он получит большую часть наследства.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <numeric>

#include <algorithm>

using namespace std;

class UnfairDivision

{

public:

int albertsShare(vector<int> assets)

{

int albert = 0, bestAlbert = 0, bestBetty, a, b;

for(a = 1; a < assets.size(); a++)

{

bestBetty = 0;

for(b = 1; b < assets.size(); b++)

{

if (a == b) continue;

int s[] = {accumulate(assets.begin(),assets.begin()+min(a,b),0),

accumulate(assets.begin() + min(a,b),

assets.begin() + max(a,b),0),

accumulate(assets.begin() + max(a,b),assets.end(),0)};

sort(s,s + 3);

if ((s[1] > bestBetty) || (s[1] == bestBetty && s[0] < albert))

{

bestBetty = s[1];

albert = s[0];

}

}

if (albert > bestAlbert) bestAlbert = albert;

}

return bestAlbert;

}

};